package org.example.dynamic_planning;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

public class Backpack_Problem_01 {
    public static void main(String[] args) {
        //01背包问题
//        int n = 1;
//        HashMap<Integer, Integer> map = new HashMap<>();
//        int[][] thing = {{2,2},{2,3},{3,1},{1,5},{5,4},{2,3}};
        Scanner sc = new Scanner(System.in);
        String nums = sc.nextLine();
        String[] numsp = nums.split(" ");
        int n = Integer.parseInt(numsp[1]);
        int size = Integer.parseInt(numsp[0]);
        String w = sc.nextLine();
        String v = sc.nextLine();
        String[] weight = w.split(" ");
        String[] value = v.split(" ");
        int[][] thing = new int[size][2];
        for (int i = 0; i < size; i++) {
            thing[i][0] = Integer.parseInt(weight[i]);
            thing[i][1] = Integer.parseInt(value[i]);
        }
        int maxValue = getMaxValue(thing,n);
        System.out.println(maxValue);
    }
    public static int getMaxValue(int[][] thing,int j){
        Arrays.sort(thing, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0],o2[0]);
            }
        });
        System.out.println(Arrays.deepToString(thing));
        int[][] dp = new int[thing.length][j+1];
        for (int[] arr : dp) {
            Arrays.fill(arr,0);
        }
        for (int i = 1; i < j+1; i++) {
            if (thing[0][0] <= i) dp[0][i] = thing[0][1];
        }
        for (int i = 1; i < thing.length; i++) {
            for (int k = 1; k < j+1; k++) {
                if (thing[i][0] > k){
                    dp[i][k] = dp[i-1][k];
                }else {
                    dp[i][k] = Math.max(dp[i-1][k],dp[i-1][k-thing[i][0]] + thing[i][1]);
                }
            }
        }
        System.out.println(Arrays.deepToString(dp));
        return dp[thing.length-1][j];
    }
}
